package com.kehao.leetcode.jzoffer;

import org.junit.Test;

import java.util.*;

/**
 * @author Kehao.Chen
 * @version 1.0
 * @date 2022/6/29 16:09
 */
public class JZSolution043 {
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    private static class CBTInserter {

        TreeNode root;
        List<TreeNode> treeNodeList = new ArrayList<>();

        public CBTInserter(TreeNode root) {
            this.root = root;
            bfs(root);
            for (int i = 0; i < treeNodeList.size(); i++) {
                TreeNode treeNode = treeNodeList.get(i);
                treeNode.left = null;
                treeNode.right = null;
            }
            for (int i = 1; i <treeNodeList.size(); i++) {
                int parentIndex = (i-1)/2;
                if(i%2==1){
                    treeNodeList.get(parentIndex).left = treeNodeList.get(i);
                }
                if(i%2==0){
                    treeNodeList.get(parentIndex).right = treeNodeList.get(i);
                }
            }
        }

        public int insert(int v) {
            TreeNode treeNode = new TreeNode(v);
            treeNodeList.add(treeNode);
            int nodeIndex = treeNodeList.size()-1;
            int parentIndex = (nodeIndex-1)/2;
            TreeNode parentNode = treeNodeList.get(parentIndex);
            if(nodeIndex%2==1){
                parentNode.left = treeNodeList.get(nodeIndex);
            }
            if(nodeIndex%2==0){
                parentNode.right = treeNodeList.get(nodeIndex);
            }
            return parentNode.val;
        }

        public TreeNode get_root() {
            return root;
        }

        private void bfs(TreeNode root){
            Queue<TreeNode> treeNodeQueue = new LinkedList<>();
            treeNodeQueue.add(root);
            while (!treeNodeQueue.isEmpty()){
                TreeNode poll = treeNodeQueue.poll();
                this.treeNodeList.add(poll);
                if(poll.left!=null){
                    treeNodeQueue.add(poll.left);
                }
                if(poll.right!=null){
                    treeNodeQueue.add(poll.right);
                }
            }
        }
    }

}
